function numWays(n: number): number {
    let arr = [1, 1];
    let i = 2;
    while (i <= n) {
        const x = (arr[i - 2] + arr[i - 1]) % 1000000007;
        arr.push(x);
        i++;
    }
    return arr[arr.length - 1]
};